1. Field of the Invention
The present invention relates to a variable-length coding device and a method thereof used for a coding device for image data. In particular, the invention relates to a variable-length coding device and a method thereof achieving reduction of power consumption by decreasing a capacity of a memory used as a table and frequency of access to the memory.
2. Description of the Background Art
A great amount of data generally contained in an image signal is compressed for transmission and recording, and the compressed data is expanded when the data is received or reproduced. One method of compressing image data is the variable-length coding system. According to this system, when an input coefficient string is to be coded, a code of a short length is assigned to a pattern of a coefficient string with a high probability of occurrence, and a code of a long length is assigned to a pattern of a coefficient string with a low probability of occurrence, thereby decreasing an average code length.
FIG. 1 shows a general structure of a coding device including a conventional variable-length coding circuit. An input image is divided into 8.times.8-pixel data, and converted to 8.times.8 coefficients representing frequency components by a discrete cosine transformation (DCT) circuit 51. The order of these coefficients is changed such that they are arranged from coefficients of lower frequency components by a sequence conversion circuit 52, and resultant coefficients are quantized by a quantizer circuit 53. The coefficients are finally coded to a variable-length code to be output by a variable-length coding circuit 54.
FIG. 2 shows a conventional variable-length coding circuit. An input coefficient string is converted by a run.level pair generation circuit 61 to a pair of run data representing the number of successive 0 coefficients and level data representing a non-zero coefficient following 0. A correspondence table storing in advance a correspondence between a pair of run data and level data and a code and code length is referred to, for outputting a code and code length corresponding to the pair of run data and level data by a code table 62. Codes output from code table 62 have various code lengths, and the codes may be converted to have fixed length by a fixed length conversion circuit (not shown) in some cases.
In general, the variable-length coding circuit does not allocate a specific variable-length code to every pair of run data and level data. To a pair of run data and level data with low probability of occurrence, a fixed length code formed of a specific escape code as a leading one and run data and level data added thereto as they are is assigned, or the pair of run data and level data with low probability of occurrence is converted to two different pairs of run data and level data having specific codes allocated thereto as shown by equation (1). EQU (R,L).fwdarw.(R-1, 0)+(0,L) (1)
In the equation above, R and L respectively represent run data and level data. Although the level data is essentially a non-zero coefficient, level data of 0 is defined by this conversion.
An example of allocation of a code to a pair of run data and level data according to this system is shown in FIG. 3. Here, instead of the code itself, a code length is used for allocation. The level data are defined as 0-255 (absolute values), and run data are defined as 0-61. If the level data is not 0, one bit representing whether the level data is positive or negative is included in a code length. An empty portion in the table corresponds to a pair of run data and level data to which no code is allocated, and the pair is converted to a pair of run data and level data having a code allocated thereto by conversion following the equation (1). For example, no code is allocated to a pair of run data and level data respectively of 10 and 20, and the pair of run data and level data is converted to two pairs of 9 and 0, and 0 and 20 based on equation (1). With reference to FIG. 3, a short code is allocated to a pair of run data and level data with a high probability of occurrence, and a long code is allocated to a pair of run data and level data with a low probability of occurrence.
FIG. 4 shows an example of a conventional variable-length coding circuit according to this system. An input coefficient string is converted by a run.level pair generation circuit 81 to a pair of run data representing the number of successive 0 coefficients and level data representing a non-zero coefficient following 0. Whether a code is allocated to a pair of run data and level data is determined by a code presence/absence determination table 82. If it is determined that a code is allocated to the pair of run data and level data, the pair is transferred to a code table 84, converted to a corresponding code and code length by reference to a correspondence table storing in advance a correspondence between a pair of run data and level data and a code and code length, and the converted one is output. If it is determined that no code is allocated to the pair, the pair is transferred to a run.level conversion circuit 83 and converted according to the equation (1). (The level data could be 0.) Consequently, two pairs of run data and level data are transferred to code table 84, and each of them is converted to a corresponding code and code length to be output.
Code presence/absence determination table 82 is structured as shown in FIG. 5 such that 1 representing allocation of a code corresponding to a pair of run data and level data or 0 representing that no code is allocated to a pair of run data and level data is stored in advance. In code table 84, a code and code length corresponding to a pair of run data and level data to which a code is allocated is stored as shown in FIG. 3.
A problem of the conventional variable length coding circuit described above is as follows.
With reference to FIG. 5, in order to be determined whether a code is allocated or not by code presence/absence determination table 82, an address of total 14 bits formed of 6 bits representing run data and 8 bits representing an absolute value of level data is necessary. The number of words is 255.times.62=15,810, and an output is 1 bit showing whether a code is allocated or not. Accordingly, a memory having a large capacity of total 15,810.times.1=15,810 bits is required. In addition, code presence/absence determination table 82 should be referred to correspondingly to all of the pairs of run data and level data generated by run.level pair generation circuit 81. The memory having a large capacity is highly frequently accessed and power consumption increases.
Referring to FIG. 3, when conversion to a code and code length is performed by code table 84, an address of total 15 bits, formed of 6 bits representing run data, 8 bits representing an absolute value of level data, and 1 bit representing whether the level data is positive or negative, is needed. The number of pairs of run data and level data which is 0 is 62, and the number of pairs of run data and level data which is not 0 is 315. As a result, the number of total words is 62+315.times.2=692. An output is total 20 bits comprised of 16 bits representing a code and 4 bits representing a code length, and a memory having a large capacity of total 692.times.20=13,840 bits is necessary. Further, code table 84 is referred to correspondingly to all of the pairs of run data and level data for which code presence/absence determination table 82 determines that codes are allocated respectively, and all of two pairs of run data and level data newly generated by run.level pair conversion circuit 83. Consequently, one access is made to a memory having a large capacity, and power consumption increases.